package star.基础.归并排序.求小和;


import star.Utils;

/*
*  比如 1 5 3 2 4 中 4 左侧有 1,3,2比 4 小,4 的小和试6,求出数组中所有的小和
*
* */
public class SmallSum {
    public static void main(String[] args) {
        int[] arr = {1,5,3,6,7,8};
        System.out.println(smallSum(arr));
        Utils.traversal(arr);
    }

    private static int smallSum(int[] arr){
        if (arr.length <= 1 || arr == null) return 0;
        return process(arr,0, arr.length-1);
    }

    private static int process(int[] arr,int L,int R){
        if (L == R) return 0;
        int mid = L + ((R - L) >> 1);
        return process(arr,L,mid) + process(arr,mid+1,R) + merge(arr,L,mid,R);
    }

    private static int merge(int[] arr,int L,int M,int R){
        int[] help = new int[R - L + 1];
        int count = 0;
        int i = 0;
        int p1 = L;
        int p2 = M+1;
        while (p1 <= M && p2 <= R){
            count += arr[p1] < arr[p2] ? (R-p2+1)*arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) help[i++] = arr[p1++];
        while (p2 <= R) help[i++] = arr[p2++];
        for (int j = 0; j < help.length; j++) {
            arr[L+j] = help[j];
        }
        return count;
    }
}
